#include "QuotaMap.h"
#include <memory.h>
#include <cassert>

#ifdef WIN32
#define BASSERT assert
#else
#define BASSERT //
#endif

#ifdef JUMPLIST_TEST

#include "JumpList.h"

void JumpList2Test()
{
	class BrokerKeyInfo{
	public:
		BrokerKeyInfo(){}
		unsigned int GetHash()const{ return 0; }
		bool operator==(const BrokerKeyInfo& bki)const{ return true; }
		bool operator<(const BrokerKeyInfo& bki)const{ return true; }
	};
	class BondComparator{
	public:
		int GetExpandLength(int count, int length){ return length * 2; }
		bool operator()(const BrokerKeyInfo&k1, const BrokerKeyInfo& k2){ return true; }
	};
	JumpList<BrokerKeyInfo, BondComparator> bondlist;
	bondlist.Insert(BrokerKeyInfo());
	bondlist.BeginPush(0);
	bondlist.Push(BrokerKeyInfo());
	bondlist.EndPush(true);
	bondlist.Erase(BrokerKeyInfo());
	bondlist.GetCount();

	vector<BrokerKeyInfo> keys;
	bondlist.GetAllKeys(keys);
	bondlist.GetKeys(0, 10, keys);

	bondlist.CheckSort();
	bondlist.CheckLink();
	bondlist.CheckState();
	bondlist.CheckLength();
	bondlist.CheckUnique();
	bondlist.CheckPool();
	bondlist.GetBytes();

	bondlist.Clear();
}
#endif
namespace qb{
	namespace ht{
		/*
			内存数据结构关系图
			哈希表
			|       |
			|       |
			|       |       [--------]   [--------]   [--------]
			|m_slots|------>[  Entry ]   [  Entry ]   [  Entry ]
			|       |       |hashnext|-->|hashnext|-->|hashnext|-->0
			|       |   0<--|hashprev|<--|hashprev|<--|hashprev|
			|       |       [________]   [________]   [________]
			|       |

			新旧双链表
			[--------]    [--------]    [--------]    [--------]
			|  Entry |    |  Entry |    |  Entry |    |  Entry |
			|listnext|--->|listnext|--->|listnext|--->|listnext|--->0
			0<--|listprev|<---|listprev|<---|listprev|<---|listprev|
			[________]    [________]    [________]    [________]
			m_tail                                    m_head


			*/
		static bool gs_quota_check = false;
		namespace{
			template<class T>
			void SwapValue(T& v1, T& v2){
				T temp = v1; v1 = v2; v2 = temp;
			}
		}
		QuotaMap::QuotaMap() :m_listener(0),
			m_slots(0), m_entry_array(0), m_head(0), m_tail(0)
		{

		}

		QuotaMap::~QuotaMap()
		{
			if (m_slots){ delete[] m_slots; m_slots = 0; }
			if (m_entry_array){ delete[] m_entry_array; m_entry_array = 0; }
		}

		void QuotaMap::Swap(QuotaMap& qm)
		{
            BASSERT(qm.m_item_size == m_item_size);
            BASSERT(qm.m_entry_size == m_entry_size);
            BASSERT(m_entry_size >= m_item_size && m_entry_size % 4 == 0);
            BASSERT(qm.m_capcity >= m_capcity);
			SwapValue<SLOT*>(m_slots, qm.m_slots);
			SwapValue<int>(m_slot_length, qm.m_slot_length);
			SwapValue<int>(m_count, qm.m_count);
			SwapValue<int>(m_capcity, qm.m_capcity);
			SwapValue<char*>(m_entry_array, qm.m_entry_array);
			SwapValue<Entry*>(m_head, qm.m_head);
			SwapValue<Entry*>(m_tail, qm.m_tail);
		}

		void QuotaMap::Build(int slot, int capcity, int itemsize)
		{
			m_slot_length = slot;
			m_capcity = capcity;
			m_count = 0;
			m_item_size = itemsize;
			m_entry_size = (itemsize / 4 + 1) * 4 + sizeof(Entry) - 4;

			m_slots = new SLOT[m_slot_length];
			memset(m_slots, 0, sizeof(SLOT)*m_slot_length);

			m_entry_array = new char[m_entry_size*m_capcity];
			memset(m_entry_array, 0, m_entry_size*m_capcity);;

			Entry* prev = 0;
			char* ptr = m_entry_array;
			m_tail = (Entry*)m_entry_array;
			m_head = (Entry*)(m_entry_array + (m_capcity - 1)*m_entry_size);
			for (int i = 0; i < m_capcity; i++)
			{
				Entry* entry = (Entry*)ptr;
				entry->rid = -1;
				entry->changed = 0;
				entry->hashnext = entry->hashprev = 0;
				entry->listnext = (Entry*)((i + 1 < m_capcity) ? (ptr + m_entry_size) : 0);
				entry->listprev = prev;
				prev = entry;
				ptr += m_entry_size;
			}
		}

		void QuotaMap::Expand(int capcity)
		{
			QuotaMap qm;
			qm.Build(m_slot_length, capcity, m_item_size);
			Entry* entry = m_tail;
			for (; entry != m_head; entry = entry->listnext)
			{
				if (entry->rid >= 0)
				{
					qm.Set(entry->rid, entry->record, 0, 0, false);
				}
			}
			Swap(qm);
		}

		void QuotaMap::Set(int rid, const void* record, int* swap_rid, char* swap_record, bool insert)
		{
			int slot = GetSlot(rid);
			Entry* entry = m_slots[slot];
			for (; entry && entry->rid != rid; entry = entry->hashnext){}
			if (!entry)
				entry = PickTail(swap_rid, swap_record);
			else
				m_count++;
            BASSERT(entry && entry->record);

			if (m_listener){ m_listener->OnWrite(rid, entry->record, record, m_item_size, insert); }
			memcpy(entry->record, record, m_item_size);
			entry->changed++;
			AdjustToHead(entry);
			AdjustId(entry, rid);
			CheckList();
		}
		void QuotaMap::CheckListHead()
		{
			if (!gs_quota_check)return;
            BASSERT(m_head && m_tail);
            BASSERT(m_head->listnext == 0 && m_tail->listprev == 0);
			//CheckSlot(m_head);
			//CheckSlot(m_tail);
		}
		void QuotaMap::CheckList()
		{
            if (!gs_quota_check)return;
            CheckListHead();
            int capcity = 0;
            Entry* entry = m_tail;
            Entry* prev = 0;
            bool valid_begin = false;
            for (; entry != 0; capcity++, entry = entry->listnext)
            {
                BASSERT(prev == entry->listprev);
                if (entry != m_head){ BASSERT(entry->listnext); }
                if (entry->rid >= 0){ valid_begin = true; }
                if (valid_begin)
                {
                    BASSERT(entry->rid >= 0);
                }
                CheckSlot(entry);
                prev = entry;
            }
            BASSERT(capcity == m_capcity);
		}
		void QuotaMap::CheckSlot(Entry* entry)
		{
            if (!gs_quota_check)return;
            BASSERT(entry);
            if (entry->rid < 0)
                return;
            bool found = false;
            int slot = GetSlot(entry->rid);
            found = CheckSlot(slot, entry);
            BASSERT(found);
		}
		bool QuotaMap::CheckSlot(int slot, Entry* entry)
		{
            if (!gs_quota_check)return true;
            BASSERT(slot >= 0 && slot < m_slot_length);
            bool found = false;
            Entry* hash = m_slots[slot];
            Entry* prev = 0;
            while (hash)
            {
                if (hash == entry){ found = true; }
                BASSERT(prev == hash->hashprev);
                BASSERT(hash->rid >= 0 && hash->changed >= 0);
                prev = hash;
                hash = hash->hashnext;
            }
            return found;
		}
		void QuotaMap::CheckHashArray()
		{
			if (!gs_quota_check)return;
			for (int i = 0; i < m_slot_length; i++)
			{
				Entry* entry = m_slots[i];
				CheckSlot(i, 0);
			}
		}
		void QuotaMap::AdjustId(Entry* et, int rid)
		{
			// 调整Entry的rid，需要将其从hash插槽中摘取出来，重新插入
			CheckListHead();
			//if (rid == et->rid)
			//	return;
			if (et->rid >= 0)
			{
				int slot = GetSlot(et->rid);
				Entry* entry = m_slots[slot];
                if (entry){ BASSERT(entry->hashprev == 0); }
				for (; entry && entry->rid != et->rid; entry = entry->hashnext){}
				if (entry)
				{
                    BASSERT(entry == et);
					Entry* prev = et->hashprev;
					Entry* next = et->hashnext;
					if (prev)prev->hashnext = next;
					if (next)next->hashprev = prev;

					if (m_slots[slot] == et)
					{
						if (next)
							next->hashprev = 0;
						m_slots[slot] = next;
					}

				}
			}

			/* 当rid有效的时候，才需要插入到哈希插槽中
				|    |
				|    |
				|slot|==>[]<==>[]<==>[]<==>[]<==>[]
				|    |   ^
				|    |
				如上，将et插入到插槽的双链表的开头
				*/
			et->rid = rid;
			if (rid >= 0)
			{
				int slot = GetSlot(rid);
				et->hashprev = 0;
				et->hashnext = m_slots[slot];
				if (m_slots[slot])
					m_slots[slot]->hashprev = et;
				m_slots[slot] = et;
			}
			CheckListHead();
		}

		QuotaMap::Entry* QuotaMap::PickTail(int* swap_rid, char* swap_record)
		{
			CheckListHead();
			if (swap_rid && swap_record && m_tail->rid >= 0)
			{
				*swap_rid = m_tail->rid;
				memcpy(swap_record, m_tail->record, m_item_size);
			}
			Entry* entry = m_tail;
			m_tail = m_tail->listnext;
			m_tail->listprev = 0;
			entry->listnext = 0;
			entry->listprev = m_head;
			m_head->listnext = entry;
			m_head = entry;
			entry->changed = 0;
			CheckListHead();
			return entry;
		}

		void QuotaMap::AdjustToHead(Entry* et)
		{
			CheckListHead();
			if (et != m_head)
			{
				Entry* prev = et->listprev;
				Entry* next = et->listnext;
				if (prev)prev->listnext = next;
				if (next)next->listprev = prev;
				if (m_tail == et)
				{
					m_tail = next;
                    BASSERT(next && next->listprev == 0);
				}
				m_head->listnext = et;
				et->listprev = m_head;
				et->listnext = 0;
				m_head = et;
			}
			CheckListHead();
		}

		bool QuotaMap::Get(int rid, char* record, bool adjust)
		{
            BASSERT(rid >= 0);
			int slot = GetSlot(rid);
			Entry* entry = m_slots[slot];
			for (; entry && entry->rid != rid; entry = entry->hashnext){}
			if (entry)
			{
				memcpy(record, entry->record, m_item_size);

				// 将此Entry放在新旧双链表的头部，使得其维持的时间更长
				if (adjust)
				{
					AdjustToHead(entry);
					CheckList();
				}
				return true;
			}
			return false;
		}

		int QuotaMap::GetMemoryUsed()const
		{
			int bytes = sizeof(QuotaMap);
			bytes += m_slot_length*sizeof(SLOT);
			bytes += m_entry_size*m_capcity;
			return bytes;
		}
		int QuotaMap::GetSlotValidCount()
		{
			int count = 0;
			for (int i = 0; i < m_slot_length; i++)
			{
				if (m_slots[i] != 0)count++;
			}
			return count;
		}
		int QuotaMap::GetSlotMaxLength(float* avgLength)
		{
			int count_max = 0;
			int slot_count = 0;
			int length_sum = 0;
			for (int i = 0; i < m_slot_length; i++)
			{
				int count = 0;
				Entry* entry = m_slots[i];
				if (entry != 0)slot_count++;
				for (; entry != 0; entry = entry->hashnext){ count++; }
				count_max = count_max < count ? count : count_max;
				length_sum += count;
			}
			if (avgLength)*avgLength = length_sum*1.0f / slot_count;
			return count_max;
		}
		int QuotaMap::GetSlot(int rid)
		{
			// 每条记录都有一个record_id,简写为rid，与其一一对应
			// 此函数将rid通过哈希计算该记录要放入的插槽m_slots中
			return rid%m_slot_length;
		}
	}//namespace ht
}//namespace qb
